In today's systems, the commodity pricing of processors, storage, network bandwidth, and basic software is continuously reducing the relative contribution of these elements to the total lifecycle cost of computing solutions. Operating and integration costs are increasing, in comparison. The research community has responded by working on approaches to automated system administration. Increasingly, large companies are consolidating data operations into extremely efficiently administered data centers.
The Database-as-a Service (DAS) model as described in US Patent Application Publication number US2004/0243816 is one example of this trend. In the DAS model, the client's database is stored at the service provider. The provider is responsible for providing adequate CPU, storage, and networking resources required to run database operations, in addition to the system administration tasks such as backup, recovery, reorganization etc.
A fundamental challenge posed by the DAS model is that of database privacy and security. In the DAS model, the user data resides on the premises of the database service provider. Most companies and individuals view their data as an asset. The theft of intellectual property already costs organizations a great amount of money every year. Therefore, the owner of the data needs to be assured that the data are protected against malicious attacks from the outside of the service provider. In addition to this, recent studies indicate that 40% of those attacks are perpetrated by the insiders. Hence, the second and more challenging problem is the privacy of the data when even the service provider itself is not trusted by the owner of the data. Data encryption is employed to ensure the privacy of the users' data.
The security of any encryption technique relies on the confidentiality of the encryption keys. Hence, key management plays an essential role in a database-as-a-service environment. Cryptographic key update transactions are an essential part of the database systems and applications. Each update transaction requires at least one invocation of the encryption function to encrypt the data in the system. The actual number of invocations depends on various factors such as the data unit subject to the encryption, i.e., the granularity of the encryption, specifics of the transaction, e.g., an insert only transaction, a transaction on a number of data objects, etc. It is known that encryption is a CPU intensive process. Therefore the key update transactions may hold locks on the certain set of database records for an extended period of time causing a decline in the system performance. Re-keying large amounts of data entails significant encryption costs and interferes with the other transactions thereby causing performance degradation in the system.